#!env python

# Write a program that given a file containing a list of words (one
# word per line, no spaces, all lower case) identifies the longest
# word in the file that can be constructed by concatenating copies of
# shorter words also found in the file.

import Queue
from threading import Thread
from processing import Process, Queue, Lock

global lock
lock = Lock()
class LongestComposition(Process):
    def __init__( self, words, wordset, result_queue ):
        Process.__init__(self)
        self.result_queue = result_queue
        self.words = words
        self.wordset = wordset
        # Intentionally not getting rid of duplicates to make it run
        # longer on sets containing duplicates.
        # self.words = list(wordset)

    def composed(self, word, suffice=True):
        if ( suffice and word in self.wordset ) :
            return True
        for i in range(1,len(word)):
            if ( 
                 # self.composed(word[0:i]) and
                word[0:i] in self.wordset and
                 self.composed(word[i:len(word)+1])):
                return True
        return False

    def run(self):
        global result
        # result = ""
        for word in self.words:
            lock.acquire()
            length = len(result)
            lock.release()
            if ( len(word) > length and 
                 self.composed(word, suffice=False )):
                lock.acquire()
                if ( len(word) > len(result) ):
                    result = word
                lock.release()
        self.result_queue.put(result)

global result
result = ""
if __name__ == "__main__":

    from optparse import OptionParser
    parser = OptionParser()
    parser.add_option("-t", "--threads", dest="threads",
                      type="int",
                      help="threads to use", default=1 )

    (options, args) = parser.parse_args()

    import sys
    words = [ i.strip() for i in sys.stdin ]
    wordset = frozenset(words)
    result_queue = Queue()

    threads = []
    thread_count = options.threads
    words_per_thread = (len(words)+thread_count-1)/thread_count;
    for i in range(thread_count):
        begin = words_per_thread * i
        end = min(len(words),begin+words_per_thread)
        lc = LongestComposition( words[begin:end],
                                 wordset, 
                                 result_queue )
        lc.start()
        threads.append(lc)
    for t in threads:
        t.join()
        print result_queue.get()

    print "Result",result
